class Solution {
public:
     vector<vector<int>> result;
      vector<int>path;
      void dfs(vector<int>& nums,int index)
      {
         result.push_back(path);
         if(index==nums.size())
         {
           return ;

         }
         
         for(int i=index;i<nums.size();i++)
         {
           path.push_back(nums[i]);
           dfs(nums,i+1);
           path.pop_back();

         }

      }
    vector<vector<int>> subsets(vector<int>& nums) {
    
    result.clear();
    path.clear();
    dfs(nums,0);
    return result;

    }
};
class Solution {
public:
    vector<vector<int>>result;
    vector<int>path;
    void dfs(vector<int>& candidates, int target,int sum,int index)
    { if(sum>target)
    {return ;}
      if(sum==target)
      {
         result.push_back(path);
      }
 
      for(int i=index;i<candidates.size();i++)
      {
         sum+=candidates[i];
         path.push_back(candidates[i]);
         dfs(candidates,target,sum,i);
         path.pop_back();
         sum-=candidates[i];
      
      }
      
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    result.clear();
    path.clear(); 
    
    dfs(candidates,target,0,0);
    return result;

    }
};
class Solution {
public:
    bool canJump(vector<int>& nums) {
     int cover=0;
     for(int i=0;i<=cover;i++)
     {
        cover=max(cover,i+nums[i]);
        if(cover>=nums.size()-1)
         return true;
    
     }

     return false;


    }
};
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m=matrix.size()-1;
    int n=0;
    while(m>=0&&n<matrix[0].size())
    {
      if(matrix[m][n]<target)
      {
       n++;
      }
      else if(matrix[m][n]>target)
      {m--;}
      else
      {
       return true;
      }

    }
    return false;




    }
};